Study Objectives: We investigated the association of HIV infection and highly active antiretroviral therapy (HAART) with sleep disordered breathing (SDB), fatigue, and sleepiness. Methods: HIV-uninfected men (HIV−; n = 60), HIV-infected men using HAART (HIV+/HAART+; n = 58), and HIV-infected men not using HAART (HIV+/HAART−; n = 41) recruited from two sites of the Multicenter AIDS cohort study (MACS) underwent a nocturnal sleep study, anthropometric assessment, and questionnaires for fatigue and the Epworth Sleepiness Scale. The prevalence of SDB in HIV- men was compared to that in men matched from the Sleep Heart Health Study (SHHS). Results: The prevalence of SDB was unexpectedly high in all groups: 86.7% for HIV−, 70.7% for HIV+/HAART+, and 73.2% for HIV+/HAART−, despite lower body-mass indices (BMI) in HIV+ groups. The higher prevalence in the HIV− men was significant in univariate analyses but not after adjustment for BMI and other variables. SDB was significantly more common in HIV− men in this study than those in SHHS, and was common in participants with BMIs <25 kg/m2. HIV+ men reported fatigue more frequently than HIV− men (25.5% vs. 6.7%; p = 0.003), but self-reported sleepiness did not differ among the three groups. Sleepiness, but not fatigue, was significantly associated with SDB. Conclusions: SDB was highly prevalent in HIV− and HIV+ men, despite a normal or slightly elevated BMI. The high rate of SDB in men who have sex with men deserves further investigation. Sleepiness, but not fatigue, was related to the presence of SDB. Clinicians caring for HIV-infected patients should distinguish between fatigue and sleepiness when considering those at risk for SDB, especially in non-obese men.